// poj2942
// 题意：已知n(<=1000)个圆桌骑士，m(<=1000000)个双向仇恨关系。如果某个骑士
//       能符合要求的以某种安排坐在圆桌边上，他就能留下来，否则就不可以。
//       可以围坐在圆桌边上的要求是：
//       1.必需要有大于1的奇数个人;
//       2.相邻两人不能有仇恨关系。
//       现在请问，最少有多少骑士不能留下来。
//
// 题解：联通性好题。这题题意有点难理解。首先取个补图，然后在补图中有边就
//       可以相邻坐。
//
//       然后可以坐在一桌的肯定是一个点双连通分量里的（当然也是边双连通
//       分量里，不过用边不太好处理）。所以我们先求出点双连通分量。
//       然后有一个性质（自己也可以yy下），如果一个点双连通分量中有一个
//       奇圈，那么对于任意点都可以被包含在某个奇圈中。然后我们只需要dfs
//       二分染色判断是否有奇圈就行，如果有，就把该连通分量的所有点都标记
//       为可以坐下。
//
//       求联通分量的时候要注意，割点可能属于多个点双连通分量里。
//     
//
// run: $exec < input
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>

int const maxn = 1007;
int const maxm = maxn * maxn * 2;
bool has_seat[maxn];
int head[maxn], next[maxm], end_point[maxm];
int alloc;
bool map[maxn][maxn];
int in_component[maxn], color[maxn];
int component_tick;

// need for tarjan
int low[maxn], dfn[maxn];
int tick;
std::stack<int> stk;

int n, m;

void init()
{
	std::memset(map, 0, sizeof(map));
	std::memset(dfn, 0, sizeof(dfn));
	std::memset(low, 0, sizeof(low));
	std::memset(head, 0, sizeof(head));
	std::memset(has_seat, 0, sizeof(has_seat));
	while (!stk.empty()) stk.pop();
	alloc = 2;
	tick = 0;
}

void add_edge(int u, int v)
{
	end_point[alloc] = v; next[alloc] = head[u]; head[u] = alloc++;
	end_point[alloc] = u; next[alloc] = head[v]; head[v] = alloc++;
}

bool dfs(int u, int co)
{
	color[u] = co;
	for (int p = head[u]; p; p = next[p]) {
		int v = end_point[p];
		if (in_component[v] != component_tick) continue;
		if (color[v] == co) return true;
		if (!color[v] && dfs(v, co ^ 1))
			return true;
	}
	return false;
}

void coloring_judge(std::vector<int> const & v)
{
	component_tick++;
	for (int i = 0; i < (int)v.size(); i++) {
		in_component[v[i]] = component_tick;
		color[v[i]] = 0;
	}

	if (dfs(v[0], 2))
		for (int i = 0; i < (int)v.size(); i++)
			has_seat[v[i]] = true;
}

void tarjan(int u, int parent)
{
	low[u] = dfn[u] = ++tick;
	stk.push(u);
	for (int p = head[u]; p; p = next[p]) {
		int v = end_point[p];
		if (v == parent) continue;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = std::min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				std::vector<int> vec;
				vec.push_back(u);
				vec.push_back(v);
				for (; stk.top() != v; stk.pop())
					vec.push_back(stk.top());
				stk.pop();
				coloring_judge(vec);
			}
		} else
			low[u] = std::min(low[u], dfn[v]);
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	while (std::cin >> n >> m && (n || m)) {
		init();
		for (int i = 0, x, y; i < m; i++) {
			std::cin >> x >> y;
			map[x][y] = map[y][x] = true;
		}

		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
				if (!map[i][j]) add_edge(i, j);

		for (int i = 1; i <= n; i++)
			if (!dfn[i]) tarjan(i, -1);

		int ans = 0;
		for (int i = 1; i <= n; i++)
			ans += has_seat[i];
		std::cout << n - ans << '\n';
	}
}

